/**
 * @author 小也
 * @create 2021/4/3 9:10
 */
public class FibonacciSearch {
    /**
     * Fibonacci数组最大长度
     */
    private static final int MAX_LENGTH = 20;
    /**
     * 构造一个Fibonacci数组
     */
    private static int[] fib(){
        int[] fi = new int[MAX_LENGTH];
        fi[0] = 1;
        fi[1] = 1;
        for (int i = 2; i < fi.length; i++){
            fi[i] = fi[i - 1] + fi[i - 2];
        }
        return fi;
    }
    public static int search(int[] arr,int x) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        int k = 0;
        int[] fib = fib();
        //找到略微大于等于x的那个分割点
        while (high > fib[k] - 1){
            k++;
        }
        //将数组扩容到F(k)-1
        int[] temp = new int[fib[k]-1];
        for(int i = 0; i < arr.length; i++){
            temp[i] = arr[i];
        }
        //超过arr数组长度的位置填充arr的最后一个元素
        for (int i = arr.length;i < fib[k]-1; i++){
            temp[i] = arr[high];
        }
        while(low <= high){
            mid = low + fib[k - 1] - 1;
            if (x < temp[mid]){
                high = mid - 1;
                k--;
            }else if(x > temp[mid]){
                low = mid + 1;
                k -= 2;
            }else{
                if (mid < high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}
